Compression-based methods for nonparametric density estimation, on-line prediction, regression and classification for time series

摘要

We address the problem of nonparametric estimation of characteristics forstationary and ergodic time series. We consider finite-alphabet time series andreal-valued ones and the following four problems: i) estimation of the(limiting) probability (or estimation of the density for real-valued timeseries), ii) on-line prediction, iii) regression and iv) classification (orso-called problems with side information). We show that so-called archivers (ordata compressors) can be used as a tool for solving these problems. Inparticular, firstly, it is proven that any so-called universal code (oruniversal data compressor) can be used as a basis for constructingasymptotically optimal methods for the above problems. (By definition, auniversal code can "compress" any sequence generated by a stationary andergodic source asymptotically till the Shannon entropy of the source.) And,secondly, we show experimentally that estimates, which are based on practicallyused methods of data compression, have a reasonable precision.